package org.algorithm.graph;

import java.util.*;

import org.algorithm.graph.bean.Edge;
import org.algorithm.graph.bean.Graph;
import org.algorithm.graph.bean.Node;

/**
 * 图基本算法
 *
 * @author ztranscript 2021/8/14 11:02
 **/
public class GraphBasic {
    public static void main(String[] args) {

    }

    /**
     * Prime 最小生成树算法
     *
     * @param graph 图
     * @return 最小生成树 边集合
     */
    public static Set<Edge> primeMST(Graph graph) {
        // 当前已经解锁的边集,按权重从小到大排序
        PriorityQueue<Edge> priorityQueue
                = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        // 已经解锁的点集
        Set<Node> nodeSet = new HashSet<>();
        // 已经考虑了的表集
        Set<Edge> edgeSet = new HashSet<>();

        // 最小生成树结果集
        Set<Edge> result = new HashSet<>();
        for (Node node : graph.nodes.values()) {
            if (!nodeSet.contains(node)) {
                nodeSet.add(node);
                for (Edge edge : node.edges) {
                    if (!edgeSet.contains(edge)) {
                        edgeSet.add(edge);
                        priorityQueue.add(edge);
                    }
                }
                while (!priorityQueue.isEmpty()) {
                    // 挑选一个最小边
                    Edge edge = priorityQueue.poll();
                    Node toNode = edge.to;
                    // 判断当前边是否含新解锁的点
                    if (!nodeSet.contains(toNode)) {
                        nodeSet.add(toNode);
                        result.add(edge);
                        // 解锁点的出度边
                        for (Edge nextEdge : toNode.edges) {
                            if (!edgeSet.contains(nextEdge)) {
                                edgeSet.add(nextEdge);
                                priorityQueue.add(nextEdge);
                            }
                        }
                    }
                }
            }
        }
        // 返回结果集
        return result;
    }

    /**
     * kruskal 最小生成树算法
     *
     * @param graph 图
     * @return 最小生成树 点集合
     */
    public static Set<Edge> kruskalMST(Graph graph) {
        // 并查集,保存联通分量
        UnionFind unionFind = new UnionFind();
        unionFind.makeSets(graph.nodes.values());
        // 优先队列,根据边权重从小到大保存
        PriorityQueue<Edge> priorityQueue
                = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        for (Edge edge : graph.edges) {
            priorityQueue.add(edge);
        }
        // 从小到大,判断当前边是否加入到最小生成树集合中
        Set<Edge> result = new HashSet<>();
        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            if (!unionFind.isSameSet(edge.from, edge.to)) {
                result.add(edge);
                unionFind.union(edge.from, edge.to);
            }
        }
        // 返回结果
        return result;
    }

    /**
     * 拓扑排序
     *
     * @param graph 有向无环图
     * @return 排序结果
     */
    public static List<Node> sortedTopology(Graph graph) {
        // key: 节点 value: 当前节点剩余的入度个数
        Map<Node, Integer> inMap = new HashMap<>();
        // 入度为 0 的节点队列
        Queue<Node> zeroInQueue = new LinkedList<>();
        for (Node node : graph.nodes.values()) {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroInQueue.add(node);
            }
        }
        // 排序结果集
        List<Node> result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()) {
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for (Node next : cur.nexts) {
                inMap.put(next, inMap.get(next) - 1);
                if (inMap.get(next) == 0) {
                    zeroInQueue.add(next);
                }
            }
        }
        // 返回结果
        return result;
    }

    /**
     * BFS
     *
     * @param node 起始点
     */
    public static void bfs(Node node) {
        if (node == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        Set<Node> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.println(cur.value);
            for (Node next : cur.nexts) {
                if (!set.contains(node)) {
                    queue.add(next);
                    set.add(next);
                }
            }
        }
    }

    /**
     * DFS
     *
     * @param node 起始点
     */
    public static void dfs(Node node) {
        if (node == null) {
            return;
        }
        Deque<Node> stack = new ArrayDeque<>();
        Set<Node> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            for (Node next : cur.nexts) {
                if (!set.contains(next)) {
                    stack.add(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }

    /**
     * 图定制并查集
     */
    public static class UnionFind {
        private Map<Node, Node> fatherMap;
        private Map<Node, Integer> sizeMap;

        public UnionFind() {
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
        }

        public void makeSets(Collection<Node> nodes) {
            fatherMap.clear();
            sizeMap.clear();
            for (Node node : nodes) {
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        private Node findFather(Node n) {
            if (fatherMap.get(n) == n) {
                return n;
            } else {
                Node newFather = findFather(fatherMap.get(n));
                fatherMap.put(n, newFather);
                return newFather;
            }
        }

        public boolean isSameSet(Node a, Node b) {
            return findFather(a) == findFather(b);
        }

        public void union(Node a, Node b) {
            if (a == null || b == null) {
                return;
            }
            Node aFather = findFather(a);
            Node bFather = findFather(b);
            if (aFather == bFather) {
                return;
            }
            int aSetSize = sizeMap.get(a);
            int bSetSize = sizeMap.get(b);
            if (aSetSize < bSetSize) {
                fatherMap.put(aFather, bFather);
                sizeMap.put(bFather, aSetSize + bSetSize);
                sizeMap.remove(aFather);
            } else {
                fatherMap.put(bFather, aFather);
                sizeMap.put(aFather, aSetSize + bSetSize);
                sizeMap.remove(bFather);
            }
        }
    }
}
